# 给定一个二维的矩阵，包含 'X' 和 'O'（字母 O）。
#
#  找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。
#
#  示例:
#
# X X X X
# X O O X
# X X O X
# X O X X
#
#
#  运行你的函数后，矩阵变为：
#
# X X X X
# X X X X
# X X X X
# X O X X
#
#
#  解释:
#
#  被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。 任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都会被
# 填充为 'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。
#  Related Topics 深度优先搜索 广度优先搜索 并查集
#  👍 288 👎 0


# leetcode submit region begin(Prohibit modification and deletion)
class Solution(object):
    def solve(self, board):
        rows = len(board)

        if rows <= 1:
            return

        cols = len(board[0])

        if cols <= 1:
            return

        visited = {}
        for col in range(0, cols):
            self.dfs(board, visited, 0, col)
            self.dfs(board, visited, rows - 1, col)

        for row in range(0, rows):
            self.dfs(board, visited, row, 0)
            self.dfs(board, visited, row, cols - 1)

        for r in range(0, rows):
            for c in range(0, cols):
                if board[r][c] == '-':
                    board[r][c] = 'O'
                elif board[r][c] == 'O':
                    board[r][c] = 'X'

    """
    :type board: List[List[str]]
    :rtype: None Do not return anything, modify board in-place instead.
    """

    # 从边界上的 O  开始作深度遍历，记录下遍历到的 点，最后遍历整个 board
    def dfs(self, board, visited, row, col):

        rows = len(board)
        cols = len(board[0])

        # 遇到边界或者相邻的不是 'O' 则结束
        # 这里必须是 ！='O'作为终止条件，会再次访问，导致深度溢出
        if row < 0 or row >= rows or col < 0 or col >= cols or board[row][col] != 'O':
            return

        board[row][col] = '-'

        self.dfs(board, visited, row - 1, col)

        self.dfs(board, visited, row + 1, col)

        self.dfs(board, visited, row, col - 1)

        self.dfs(board, visited, row, col + 1)

# leetcode submit region end(Prohibit modification and deletion)
